#include "BTreeNode.h"

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	RC rc;
	// Zero out the buffer
	memset(buffer, 0, PageFile::PAGE_SIZE);
	// Try to read into the buffer
	rc = pf.read(pid, buffer);
	
	// Return error if error from PageFile read
	if (rc != 0) {
		return rc;
	}
	// Return 0 for success
	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	RC rc;
	// Try to write from the buffer into the PageFile
	rc = pf.write(pid, buffer);
	
	// Return error if error from PageFile write
	if (rc != 0) {
		return rc;
	}
	
	// Return 0 for success
	return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	int count = 0;
	int s_rid = sizeof(RecordId);	// Size of RecordId
	int s_entry = s_rid + sizeof(int);	// Add on size of key for size of entry
	int end = PageFile::PAGE_SIZE - sizeof(PageId);	// End of keys
	
	// Scan the buffer and count each key that is not 0
	// Start at first key that is after the first RecordId,
	// and increment one entry size for each key
	for (int i = s_rid; i < end; i += s_entry) {
		if ( *((int*) &buffer[i]) > 0)	// Access the key from the RecordId's pointer
			count++;
		else 	// Stop if we get to a key that is 0 because the rest isn't filled yet
			break;
	}
	
	return count; 
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	// Size of each RecordId + key (entry)
	int s_rid = sizeof(RecordId);
	int s_key = sizeof(key);
	int s_entry = s_rid + s_key;
	
	// Number of keys in the current node
	int keyCount = getKeyCount();
	
	// Number of nodes that will fit in the page
	int maxCount = PageFile::PAGE_SIZE / s_entry;
	
	// Return error if node is too full
	if (keyCount >= maxCount) {
		return RC_NODE_FULL;
	}
	
	// Inserting algorithm: 
	// 1. Scan through all keys until bigger key is found
	int i = s_rid;
	int end = keyCount * s_entry;
	while ( i < end ) {
		// If a bigger key is found, insert rid and key into proper spot
		if ( *((int*) &buffer[i]) > key ) {
			// Smaller key and RecordId of smaller key
			RecordId smaller_rid = rid;
			int smaller_key = key;
			
			// Bigger key and RecordId of bigger key
			RecordId bigger_rid;
			int bigger_key;
		
			// Go through the rest of the buffer to translocate the record
			while ( *((int*) &buffer[i]) > 0 ) {
				// Temporarily store bigger rid and key
				// Has to adjust memory to beginning of record
				memcpy(&bigger_rid, &buffer[i - s_rid], s_rid);	
				memcpy(&bigger_key, &buffer[i], s_key);
				
				// Copy smaller rid and key into buffer
				memcpy(&buffer[i - s_rid], &smaller_rid, s_rid);
				memcpy(&buffer[i], &smaller_key, s_key);
				
				// Move bigger values into smaller values for next record
				smaller_rid = bigger_rid;
				smaller_key = bigger_key;
				
				// Increase to next entry
				i += s_entry;
			}
			// Insert the last record into the buffer
			memcpy(&buffer[i - s_rid], &smaller_rid, s_rid);
			memcpy(&buffer[i], &smaller_key, s_key);
			
			// Return 0 for success
			return 0;
		}
		// Increment to next entry if not a bigger key
		i += s_entry;
	}
	
	// 2. If no bigger key, then insert into end of buffer
	memcpy(&buffer[i - s_rid], &rid, s_rid);
	memcpy(&buffer[i], &key, s_key);
	
	// Return 0 for success
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	RC rc;
	
	// Size of each RecordId + key (entry)
	int s_rid = sizeof(RecordId);
	int s_key = sizeof(key);
	int s_entry = s_rid + s_key;
	
	// Insert the record into the node; return error if node full
	rc = insert(key, rid);
	if (rc != 0) {
		return rc;
	}
	
	// Number of keys in the buffer after inserting new record
	int keyCount = getKeyCount();
	
	// Set the sibling key by getting the midpoint key of this buffer
	siblingKey = *((int*) &buffer[keyCount/2 * s_entry + s_rid]);
	
	// Fill in sibling's buffer from midpoint to end
	int end = keyCount * s_entry;
	int midpoint = keyCount/2 * s_entry;
	for(int i = midpoint; i < end; i += s_entry) {
		RecordId temp;
		memcpy(&temp, &buffer[i], s_rid);
		sibling.insert(*((int*) &buffer[i + s_rid]), temp);
	}
	
	// Zero out the rest of this node's buffer
	memset(&buffer[midpoint], 0, PageFile::PAGE_SIZE - midpoint);
	
	// Return 0 for success
	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int s_rid = sizeof(RecordId);
	int s_key = sizeof(int);
	int s_entry = s_rid + s_key;

	int end = getKeyCount() * s_entry;
	// Scan node and find key value larger or equal to searchKey
	for (int i = s_rid; i < end; i += s_entry) {
		if (*((int*) &buffer[i]) >= searchKey) {
			// Set eid (entry id) and return success
			eid = i / s_entry;
			return 0;
		}
	}
	// Return error if could not locate
	return RC_END_OF_TREE; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	int s_rid = sizeof(RecordId);
	int s_key = sizeof(int);
	int s_entry = s_rid + s_key;
	
	// Get location of entry
	int loc = eid * s_entry;
	// If entry is valid, return key and rid
	if (loc < PageFile::PAGE_SIZE - s_entry) {
		memcpy(&key, &buffer[loc + s_rid], s_key);
		memcpy(&rid, &buffer[loc], s_rid);
	
		// Return 0 for success
		return 0;
	}
	
	// Return error code if entry not found
	return RC_END_OF_TREE;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	int s_pid = sizeof(PageId);
	
	// Return the next node by accessing the PageId pointer
	return *((PageId*) &buffer[PageFile::PAGE_SIZE - s_pid]);
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	int s_pid = sizeof(PageId);
	
	// Set the location in the buffer for pid
	memcpy(&buffer[PageFile::PAGE_SIZE - s_pid], &pid, s_pid);
	return 0; 
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	RC rc;
	// Zero out the buffer
	memset(buffer, 0, PageFile::PAGE_SIZE);
	// Try to read into the buffer
	rc = pf.read(pid, buffer);
	
	// Return error if error from PageFile read
	if (rc != 0) {
		return rc;
	}
	// Return 0 for success
	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	RC rc;
	// Try to write from the buffer into the PageFile
	rc = pf.write(pid, buffer);
	
	// Return error if error from PageFile write
	if (rc != 0) {
		return rc;
	}
	
	// Return 0 for success
	return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	int count = 0;
	int s_pid = sizeof(PageId);	// Size of RecordId
	int s_entry = s_pid + sizeof(int);	// Add on size of key for size of entry
	int end = PageFile::PAGE_SIZE - s_entry;	// End of page records
	
	// Scan the buffer and count each key that is not 0
	// Start at first key that is after the first RecordId,
	// and increment one entry size for each key
	for (int i = s_pid; i < end; i += s_entry) {
		// Access the key from the PageId's pointer
		if ( *((int*) &buffer[i]) > 0)	
			count++;
	}
	
	return count;  
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
// Size of each RecordId + key (entry)
	int s_pid = sizeof(PageId);
	int s_key = sizeof(key);
	int s_entry = s_pid + s_key;
	
	// Number of keys in the current node
	int keyCount = getKeyCount();
	
	// Number of nodes that will fit in the page
	int maxCount = (PageFile::PAGE_SIZE - s_pid) /  s_entry;
	
	// Return error if node is too full
	if (keyCount >= maxCount) {
		return RC_NODE_FULL;
	}
	
	// Inserting algorithm: 
	// 1. Scan through all keys until bigger key is found
	int i = s_pid;
	int end = keyCount * s_entry;
	while ( i < end ) {
		// If a bigger key is found, insert rid and key into proper spot
		if ( *((int*) &buffer[i]) > key ) {
			// Smaller key and PagedId of smaller key
			PageId smaller_pid = pid;
			int smaller_key = key;
			
			// Bigger key and PageId of bigger key
			PageId bigger_pid;
			int bigger_key;
		
			// Go through the rest of the buffer to translocate the record
			while ( *((int*) &buffer[i]) > 0 ) {
				// Temporarily store bigger rid and key
				// Has to adjust memory to beginning of record
				memcpy(&bigger_pid, &buffer[i + s_key], s_pid);	
				memcpy(&bigger_key, &buffer[i], s_key);
				
				// Copy smaller rid and key into buffer
				memcpy(&buffer[i + s_key], &smaller_pid, s_pid);
				memcpy(&buffer[i], &smaller_key, s_key);
				
				// Move bigger values into smaller values for next record
				smaller_pid = bigger_pid;
				smaller_key = bigger_key;
				
				// Increase to next entry
				i += s_entry;
			}
			// Insert the last record into the buffer
			memcpy(&buffer[i + s_key], &smaller_pid, s_pid);
			memcpy(&buffer[i], &smaller_key, s_key);
			
			// Return 0 for success
			return 0;
		}
		// Increment to next entry if not a bigger key
		i += s_entry;
	}
	
	// 2. If no bigger key, then insert into end of buffer
	memcpy(&buffer[i + s_pid], &pid, s_pid);
	memcpy(&buffer[i], &key, s_key);
	
	// Return 0 for success
	return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	RC rc;
	
	// Size of each PageId + key (entry)
	int s_pid = sizeof(PageId);
	int s_key = sizeof(key);
	int s_entry = s_pid + s_key;
	
	// Insert the record into the node; return error if node full
	rc = insert(key, pid);
	if (rc != 0) {
		return rc;
	}
	
	// Number of keys in the buffer after inserting new record
	int keyCount = getKeyCount();
	
	// Set the sibling key by getting the midpoint key of this buffer
	midKey = *((int*) &buffer[keyCount/2 * s_entry + s_pid]);
	
	// Fill in sibling's buffer from midpoint to end
	int end = keyCount * s_entry;
	int midpoint = keyCount/2 * s_entry;
	for(int i = midpoint; i < end; i += s_entry) {
		PageId temp;
		memcpy(&temp, &buffer[i], s_pid);
		sibling.insert(*((int*) &buffer[i]), temp);
	}
	
	// Zero out the rest of this node's buffer
	memset(&buffer[midpoint], 0, PageFile::PAGE_SIZE - midpoint);
	
	// Return 0 for success
	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	int s_pid = sizeof(PageId);
	int s_key = sizeof(int);
	int s_entry = s_pid + s_key;

	int end = PageFile::PAGE_SIZE;
	// Scan node and find matching searchKey; ignore 0 values
	for (int i = s_pid; i < end; i += s_entry) {
		if (*((int*) &buffer[i]) > 0 && searchKey >= *((int*) &buffer[i])) {
			// Set pid (page id) and return success
			pid = *((PageId *) &buffer[i + s_key]);
			return 0;
		}
	}
	// Return error if could not locate
	return RC_END_OF_TREE; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	int s_pid = sizeof(PageId);
	int s_key = sizeof(int);
	
	// Zero out buffer
	memset(buffer, 0, PageFile::PAGE_SIZE);
	// Set the first PageId
	memcpy(&buffer[0], &pid1, s_pid);
	// Set first key
	memcpy(&buffer[s_pid], &key, s_key);
	// Set second pid
	memcpy(&buffer[s_pid + s_key], &pid2, s_pid);

	return 0;
}
